package Heap;

public class _134_GasStation {
    public int canCompleteCircuit_0(int[] gas, int[] cost) {
        int len = gas.length;
        int[] res = new int[len];
        for (int i = 0; i < len; i++) {
            res[i] = gas[i] - cost[i];
        }
        int index = -1;
        for (int i = 0; i < len; i++) {
            int sum = 0;
            int count = 0;
            int start = i;
            while (count < len) {
                sum += res[start];
                if (sum < 0) {
                    break;
                } else {
                    count++;
                    start = (start + 1) % len;
                }
            }
            if (sum >= 0) {
                index = i;
            }
        }
        return index;
    }

    public int canCompleteCircuit(int[] gas, int[] cost) {
        int len = gas.length;
        int index = 0;
        int sum = 0;
        int cum = 0;
        for (int i = 0; i < len; i++) {
            int fuel = gas[i] - cost[i];
            sum += fuel;
            cum += fuel;
            if (cum < 0) {
                cum = 0;
                index = i + 1;
                if (index == len) {
                    return -1;
                }
            }
        }
        return sum < 0 ? -1 : index;
    }
}
